從今天開始，我們終於可以開始真正地介紹演算法了！首先我們要介紹的是一切演算法的根本：「枚舉法」

前言

枚舉可以說是演算法設計的根本，核心精神是利用電腦高速計算的能力，暴力地嘗試所有可能後，找出答案。

我知道這乍聽之下很沒有技術含量、感覺好像只會基本語法就能掌握，但枚舉難的地方在於「什麼時候可以枚舉？」、「怎麼有效地枚舉？」、「要怎麼實作？」

枚舉的技巧

本段將介紹一些常見的枚舉技巧

定迴圈枚舉

問題可以透過固定數量的迴圈進行枚舉，這邊稱它為「定迴圈枚舉」

例題 1

Zerojudge f312 人力分配

有一個公司有 個員工，還有兩個工廠。如果工廠一與工廠二分別有 與 個員工，兩個工廠的收益 分別會是

請你考慮所有分配員工的方式，找出收益最大的組合，輸出最大收益。

注意，每個員工皆需分配到其中一個工廠。

解法

對於一些不習慣枚舉的人，可能會想要試著用微分之類的方法去推函數極值，但其實完全沒必要！

看看我們的輸入 ，才到 100 而已，完全可以暴力枚舉所有可能求解，因此如下程式碼即可通過：

int a1, b1, c1;
int a2, b2, c2;

int f1(int x) {
    return a1 * x * x + b1 * x + c1;
}

int f2(int x) {
    return a2 * x * x + b2 * x + c2;
}

void solve() {
    cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2;
    int n;
    cin >> n;
    
    int ans = INT_MIN;
    for (int i = 0; i <= n; ++i) {
        ans = max(ans, f1(i) + f2(n - i));
    }
    cout << ans << "\n";
}

例題 2

Codeforces 1490C

有 個詢問，每組詢問給定一個正整數 ，詢問是否找得到兩個正整數 滿足 ？

解法

因為 比較大一點，因此需要評估一下要怎麼枚舉了。

因為 ，因此只要在 之間枚舉 ，即可知道 ，因此只要單個迴圈即可枚舉：

void solve() {
    long long x;
    cin >> x;
    for (long long a = 1; a * a * a <= x; ++a) {
        long long b = cbrt(x - a * a * a);
        if (b > 0 && b * b * b == x - a * a * a) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

全排列枚舉

當問題只需要枚舉所有可能的排列時，這邊稱之為全排列枚舉

例題 1

Zerojudge e446 排列生成

顧名思義，這題就是要你生出 所有的排列。

解法

輸出所有排列？你會發現你很難透過迴圈來達成這件事，不過幸好 C++ 標準函式庫有提供一個工具 std::next_permutation ，它會給出一個序列的下一個排列，因此搭配 do-while 迴圈使用即可生成所有排列。

而且看看 cppreference 怎麼描述它的時間複雜度：

At most N/2 swaps, where N = std::distance(first, last). Averaged over the entire sequence of permutations, typical implementations use about 3 comparisons and 1.5 swaps per call.

雖然最多 次交換，不過對於生成某固定序列的所有排列，平均 3 次比較與 1.5 次交換，這明顯是 。

因此我們的程式可以如下撰寫：

void solve() {
    int n;
    cin >> n;
    vector<int> vec(n);
    iota(vec.begin(), vec.end(), 1);
    do {
        string s;
        for (int i = 0; i < n; ++i) {
            s += to_string(vec[i]);
            if (i != n - 1) s += ' ';
        }
        puts(s.c_str());
    } while (next_permutation(vec.begin(), vec.end()));
}

之所以改用 puts 是因為 zerojudge 系統好像變慢了，需要快一點點的 I/O

這樣我們的時間複雜度是

例題 2

CSES 1624 Chessboard and Queens

非常經典的八皇后問題，你一個 盤面，求有幾種放法能放8隻皇后，並使皇后彼此不會互相攻擊到？

皇后可橫走、直走、斜走，且格數不限，她路徑上所有的棋子都有被攻擊的可能

為了增加問題難度，盤面上有些位子會被「保留」，皇后不能被放在保留的格子上，但皇后可以跨過格子進行攻擊。

解法

你可能會想枚舉所有皇后可能的位置，但這樣一來步驟數就變成 ，根本不可能跑完！

不過可以發現，因為皇后不能待在同一列，因此 列每列必有一枚皇后；所以我們可以枚舉每個皇后在每行中的排列，再檢查目前排列是否符合題目要求即可解決，這樣步驟數會是 可以輕鬆跑完。

char board[8][9];

void solve() {
    for (int i = 0; i < 8; ++i) cin >> board[i];
    
    vector<int> queen(8);
    iota(queen.begin(), queen.end(), 0);
    
    int ans = 0;
    do {
        bool used[2][15] = {};
        bool ok = true;
        for (int i = 0; i < 8; ++i) {
            if (board[i][queen[i]] == '*' || used[0][i + queen[i]] || used[1][i - queen[i] + 7]) {
                ok = false;
                break;
            }
            used[0][i + queen[i]] = used[1][i - queen[i] + 7] = true;
        }
        if (ok) ++ans;
    } while (next_permutation(queen.begin(), queen.end()));
    
    cout << ans << "\n";
}

小結

今天先到這邊，明天會繼續講枚舉的主題，請各位敬請期待！